<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>【Trie树&amp;AC自动机】P3879[TJOI2010]阅读理解 P3808 【模板】AC自动机（简单版）P3796 【模板】AC自动机（加强版）.md | 蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。  洛谷 P3879[TJOI2010]阅读理解 ​ ​    #include  ​    #inc">
<meta property="og:type" content="article">
<meta property="og:title" content="【Trie树&amp;AC自动机】P3879[TJOI2010]阅读理解 P3808 【模板】AC自动机（简单版）P3796 【模板】AC自动机（加强版）.md">
<meta property="og:url" content="http://example.com/1111/11/11/%E3%80%90Trie%E6%A0%91&AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E3%80%91P3879[TJOI2010]%E9%98%85%E8%AF%BB%E7%90%86%E8%A7%A3%20P3808%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E7%AE%80%E5%8D%95%E7%89%88%EF%BC%89P3796%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E5%8A%A0%E5%BC%BA%E7%89%88%EF%BC%89/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。  洛谷 P3879[TJOI2010]阅读理解 ​ ​    #include  ​    #inc">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="1111-11-11T03:06:11.000Z">
<meta property="article:modified_time" content="2022-05-06T07:18:39.402Z">
<meta property="article:author" content="StarsWhisper">
<meta property="article:tag" content="OldBlog(Before20220505)">
<meta property="article:tag" content="字符串">
<meta property="article:tag" content="AC自动机">
<meta property="article:tag" content="Trie树">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main"><article id="post-【Trie树&amp;AC自动机】P3879[TJOI2010]阅读理解 P3808 【模板】AC自动机（简单版）P3796 【模板】AC自动机（加强版）" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90Trie%E6%A0%91&AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E3%80%91P3879%5BTJOI2010%5D%E9%98%85%E8%AF%BB%E7%90%86%E8%A7%A3%20P3808%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E7%AE%80%E5%8D%95%E7%89%88%EF%BC%89P3796%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E5%8A%A0%E5%BC%BA%E7%89%88%EF%BC%89/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      【Trie树&amp;AC自动机】P3879[TJOI2010]阅读理解 P3808 【模板】AC自动机（简单版）P3796 【模板】AC自动机（加强版）.md
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%AD%97%E7%AC%A6%E4%B8%B2/">字符串</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="洛谷-p3879tjoi2010阅读理解"><a class="markdownIt-Anchor" href="#洛谷-p3879tjoi2010阅读理解"></a> 洛谷 P3879[TJOI2010]阅读理解</h2>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstdlib><br />
​    #include <cstring><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <string><br />
​    #include <queue><br />
​    #include <vector><br />
​    #include <stack><br />
​    #include <map><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int INF = 0x7fffffff, SCF = 0x3fffffff;<br />
​    const int N = 5e6+4, M = 1e3+4;<br />
​    int n,m,k;<br />
​    int idx,len,ans;<br />
​    int has[M];<br />
​    char ss[22];<br />
​    struct TT<br />
​    {<br />
​        int nxt[26],id;<br />
​    }tree[N];<br />
​    void jointree(int rt)<br />
​    {<br />
​        len = strlen(ss);<br />
​        for(int i=0; i&lt;len; i++){<br />
​            int pp = ss[i]-‘a’;<br />
​            if(!tree[rt].nxt[pp]){<br />
​                tree[rt].nxt[pp] = idx++;<br />
​            }<br />
​            rt = tree[rt].nxt[pp];<br />
​        }<br />
​        tree[rt].id = 1;<br />
​    }<br />
​    void qry(int rt)<br />
​    {<br />
​        int root = rt;<br />
​        for(int i=0; i&lt;len; i++){<br />
​            int pp = ss[i]-‘a’;<br />
​            if(!tree[rt].nxt[pp]) return ;<br />
​            rt = tree[rt].nxt[pp];<br />
​        }<br />
​        has[root] = tree[rt].id;<br />
​    }<br />
​    void solve()<br />
​    {<br />
​        memset(has,0,sizeof(has));<br />
​        len = strlen(ss);<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            qry(i);<br />
​        }<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            if(has[i]) printf(&quot;%d “,i);<br />
​        }<br />
​        printf(”\n&quot;);<br />
​    }<br />
​    int main()<br />
​    {<br />
​        scanf(&quot;%d&quot;,&amp;n);<br />
​        idx = n+1;<br />
​        for(int i=1; i&lt;=n; i++){<br />
​            scanf(&quot;%d&quot;,&amp;k);<br />
​            for(int j=1; j&lt;=k; j++){<br />
​                scanf(&quot;%s&quot;,ss);<br />
​                jointree(i);<br />
​            }<br />
​        }<br />
​        scanf(&quot;%d&quot;,&amp;m);<br />
​        for(int i=0; i&lt;m; i++){<br />
​            scanf(&quot;%s&quot;,ss);<br />
​            solve();<br />
​        }<br />
​        return 0;<br />
​    }</p>
<p>​</p>
<h2 id="洛谷-p3808-模板ac自动机简单版"><a class="markdownIt-Anchor" href="#洛谷-p3808-模板ac自动机简单版"></a> 洛谷 P3808 【模板】AC自动机（简单版）</h2>
<p>​<br />
​    #include <iostream><br />
​    #include <cstdio><br />
​    #include <cstdlib><br />
​    #include <cstring><br />
​    #include <cmath><br />
​    #include <algorithm><br />
​    #include <string><br />
​    #include <queue><br />
​    #include <vector><br />
​    #include <stack><br />
​    #include <map><br />
​    #include <set><br />
​    typedef long long int LL;<br />
​    const int INF = 0x7fffffff, SCF = 0x3fffffff;<br />
​    const int N = 1e7+4, M = 1e3+4;<br />
​    int n,idx;<br />
​    char ss[N];<br />
​    struct TT<br />
​    {<br />
​        int fail,id,nxt[26];<br />
​    }tree[N];<br />
​    void joinTree()<br />
​    {<br />
​        int len = strlen(ss), rt = 0;<br />
​        for(int i=0; i&lt;len; i++){<br />
​            int pp = ss[i]-‘a’;<br />
​            if(!tree[rt].nxt[pp]){<br />
​                tree[rt].nxt[pp] = idx++;<br />
​            }<br />
​            rt = tree[rt].nxt[pp];<br />
​        }<br />
​        tree[rt].id += 1;<br />
​    }<br />
​    void getFail()<br />
​    {<br />
​        std::queue<int> q;<br />
​        int x,y,fail;<br />
​        for(int i=0; i&lt;26; i++){<br />
​            y = tree[0].nxt[i];<br />
​            if(y&gt;0){<br />
​                tree[y].fail = 0;<br />
​                q.push(y);<br />
​            }<br />
​        }<br />
​        while(!q.empty()){<br />
​            x = q.front(); q.pop();<br />
​            fail = tree[x].fail;<br />
​            for(int i=0; i&lt;26; i++){<br />
​                y = tree[x].nxt[i];<br />
​                if(y&gt;0){<br />
​                    tree[y].fail = tree[fail].nxt[i];<br />
​                    q.push(y);<br />
​                }<br />
​                else tree[x].nxt[i] = tree[fail].nxt[i];<br />
​            }<br />
​        }<br />
​    }<br />
​    int ACgo()<br />
​    {<br />
​        int rt = 0,len = strlen(ss),ans = 0;<br />
​        for(int i=0; i&lt;len; i++){<br />
​            rt = tree[rt].nxt[ss[i]-‘a’];<br />
​            for(int j=rt; j &amp;&amp; tree[j].id != -1; j=tree[j].fail){<br />
​                ans += tree[j].id;<br />
​                tree[j].id = -1;<br />
​            }<br />
​        }<br />
​        return ans;<br />
​    }<br />
​    int main()<br />
​    {<br />
​        //freopen(“D:\EdgeDownloadPlace\P3808_2.in”,“r”,stdin);<br />
​        idx = 1;<br />
​        scanf(&quot;%d&quot;,&amp;n);<br />
​        while(n–){<br />
​            scanf(&quot;%s&quot;,ss);<br />
​            joinTree();<br />
​        }<br />
​        getFail();<br />
​        scanf(&quot;%s&quot;,ss);<br />
​        printf(&quot;%d&quot;,ACgo());<br />
​        return 0;<br />
​    }</p>
<h2 id="洛谷-p3796-模板ac自动机加强版"><a class="markdownIt-Anchor" href="#洛谷-p3796-模板ac自动机加强版"></a> 洛谷 P3796 【模板】AC自动机（加强版）</h2>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;string&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> <span class="type">int</span> LL;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> INF = <span class="number">0x7fffffff</span>, SCF = <span class="number">0x3fffffff</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">1e6</span>+<span class="number">4</span>, M = <span class="number">10550</span>;</span><br><span class="line"><span class="type">int</span> n;</span><br><span class="line"><span class="type">int</span> idx;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">TT</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> fail,id,nxt[<span class="number">26</span>];</span><br><span class="line">&#125;node[M];</span><br><span class="line"><span class="type">char</span> ss[N];</span><br><span class="line"><span class="type">char</span> sub[<span class="number">155</span>][<span class="number">75</span>];</span><br><span class="line"><span class="type">int</span> save[<span class="number">155</span>];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">initial</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;=idx; i++)&#123;</span><br><span class="line">        <span class="built_in">memset</span>(node[i].nxt,<span class="number">0</span>,<span class="built_in">sizeof</span>(node[i].nxt));</span><br><span class="line">        node[i].fail = <span class="number">0</span>;</span><br><span class="line">        node[i].id = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    idx = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">memset</span>(save,<span class="number">0</span>,<span class="built_in">sizeof</span>(save));</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">joinTree</span><span class="params">(<span class="type">int</span> id)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> len = <span class="built_in">strlen</span>(sub[id]) ,rt = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;len; i++)&#123;</span><br><span class="line">        <span class="type">int</span> ch = sub[id][i]-<span class="string">&#x27;a&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span>(!node[rt].nxt[ch]) node[rt].nxt[ch] = ++idx;</span><br><span class="line">        rt = node[rt].nxt[ch];</span><br><span class="line">    &#125;</span><br><span class="line">    node[rt].id = id;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">buildFail</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    std::queue&lt;<span class="type">int</span> &gt;q;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;<span class="number">26</span>; i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(node[<span class="number">0</span>].nxt[i]&gt;<span class="number">0</span>) &#123;</span><br><span class="line">            node[node[<span class="number">0</span>].nxt[i]].fail = <span class="number">0</span>;</span><br><span class="line">            q.<span class="built_in">push</span>(node[<span class="number">0</span>].nxt[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!q.<span class="built_in">empty</span>())&#123;</span><br><span class="line">        <span class="type">int</span> cur = q.<span class="built_in">front</span>(); q.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="type">int</span> fail = node[cur].fail;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;<span class="number">26</span>; i++)&#123;</span><br><span class="line">            <span class="type">int</span> next = node[cur].nxt[i];</span><br><span class="line">            <span class="keyword">if</span>(next&gt;<span class="number">0</span>)&#123;</span><br><span class="line">                node[next].fail = node[fail].nxt[i];</span><br><span class="line">                q.<span class="built_in">push</span>(next);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> node[cur].nxt[i] = node[fail].nxt[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">ACgo</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> len = <span class="built_in">strlen</span>(ss),rt = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;len; i++)&#123;</span><br><span class="line">        rt = node[rt].nxt[ss[i]-<span class="string">&#x27;a&#x27;</span>];</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=rt; j; j=node[j].fail)</span><br><span class="line">            save[node[j].id] += <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">//freopen(&quot;D:\\EdgeDownloadPlace\\P3796_1.in&quot;,&quot;r&quot;,stdin);</span></span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n))&#123;</span><br><span class="line">        <span class="keyword">if</span>(n == <span class="number">0</span>) <span class="keyword">break</span>;</span><br><span class="line">        <span class="built_in">initial</span>();</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,sub[i]);</span><br><span class="line">            <span class="built_in">joinTree</span>(i);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">buildFail</span>();</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,ss);</span><br><span class="line">        <span class="built_in">ACgo</span>();</span><br><span class="line">        <span class="type">int</span> mx = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">            mx = std::<span class="built_in">max</span>(save[i],mx);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,mx);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(save[i] == mx)&#123;</span><br><span class="line">                <span class="built_in">printf</span>(<span class="string">&quot;%s\n&quot;</span>,sub[i]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90Trie%E6%A0%91&AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E3%80%91P3879[TJOI2010]%E9%98%85%E8%AF%BB%E7%90%86%E8%A7%A3%20P3808%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E7%AE%80%E5%8D%95%E7%89%88%EF%BC%89P3796%20%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91AC%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88%E5%8A%A0%E5%BC%BA%E7%89%88%EF%BC%89/" data-id="cl2uhoec2001ce4j32ycqbr2u" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/AC%E8%87%AA%E5%8A%A8%E6%9C%BA/" rel="tag">AC自动机</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Trie%E6%A0%91/" rel="tag">Trie树</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E5%AD%97%E7%AC%A6%E4%B8%B2/" rel="tag">字符串</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/1111/11/11/%E3%80%90LCA%E7%BB%83%E4%B9%A0%20%E5%80%8D%E5%A2%9E%20tarjin%E3%80%91%20%E6%B4%9B%E8%B0%B7P3379%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%20P1967%E8%B4%A7%E8%BD%A6%E8%BF%90%E8%BE%93/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">上一篇</strong>
      <div class="article-nav-title">
        
          【LCA练习 倍增 tarjin】 洛谷P3379【模板】最近公共祖先 P1967货车运输.md
        
      </div>
    </a>
  
  
    <a href="/1111/11/11/%E3%80%90tarjin%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0%20%E7%BC%A9%E7%82%B9%EF%BC%8C%E5%89%B2%E7%82%B9%EF%BC%8C%E5%89%B2%E8%BE%B9%E3%80%91%E6%B4%9B%E8%B0%B7_P3387%E7%BC%A9%E7%82%B9%E6%A8%A1%E6%9D%BFP3388%E5%89%B2%E7%82%B9%E6%A8%A1%E6%9D%BF%20HDU4738%20caocao%E2%80%98bridge/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">下一篇</strong>
      <div class="article-nav-title">【tarjin算法练习 缩点，割点，割边】洛谷_P3387缩点模板P3388割点模板 HDU4738 caocao‘bridge.md</div>
    </a>
  
</nav>

  
</article>



</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>